package com.zhupf.递归;

import sun.applet.AppletResourceLoader;

/**
 * @author zhupf
 * @date 2025年02月11日 11:09
 * @Description 60. 排列序列
 * 给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
 * <p>
 * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
 * <p>
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * 给定 n 和 k，返回第 k 个排列。
 */

public class GetPermutation {

    public static void main(String[] args) {
        GetPermutation g = new GetPermutation();
        System.out.println(g.getPermutation(3, 3));
    }


    public String getPermutation(int n, int k) {
        int[] jumpNum = new int[n+1];
        int[] used = new int[n+1];
        jumpNum[0] = 1;
        for(int i = 1;i<=n;i++){
            jumpNum[i] = jumpNum[i-1]*i;
        }
        StringBuffer sb = new StringBuffer();
        process(used,n,k,jumpNum,sb,0);
        return sb.toString();
    }

    public void process(int[] used,int n , int k,int[] jumpNum,StringBuffer sb,int idx){
        if(idx == n){
            return;
        }
        int cnt = jumpNum[n-idx-1];
        for(int i = 1;i<=n;i++){
            if(used[i] == 1){
                continue;
            }
            if(k>cnt){
                k-=cnt;
                continue;
            }
            used[i] = 1;
            sb.append(i);
            break;
        }
        process(used,n,k,jumpNum,sb,idx+1);
    }



    public String getPermutation1(int n, int k) {
        int[] num = new int[n];
        for (int a = 0; a < n; a++) {
            num[a] = a + 1;
        }
        if (k != 1) {
            int res = 1;
            int i = 1;
            for (; i <= n; i++) {
                int sum = res * (i + 1);
                if (sum > k) {
                    break;
                }
                res = sum;
            }
            num = process1(num, k, n - i, res,i);
        }
        StringBuffer sb = new StringBuffer();
        for (int a = 0; a < n; a++) {
            sb.append(num[a]);
        }
        return sb.toString();
    }

    public int[] process1(int[] num, int k, int i, int sum,int deep) {
        int res = k % sum == 0 ? k / sum - 1 : k / sum;
        if(res != 0){
            int tmp = num[i - 1];
            num[i - 1] = num[i - 1 + res];
            for (int j = i; j <= i - 1 + res; j++) {
                int t = num[j];
                num[j] = tmp;
                tmp = t;
            }
        }
        if (k % sum == 0) {
            int last = num.length - 1;
            for (int j = 0; i + j < last - j; j++) {
                int t = num[i + j];
                num[i + j] = num[last - j];
                num[last - j] = t;
            }
            return num;
        }
        return process1(num, k % sum, i + 1, sum / deep,deep-1);
    }

}
